“Physical network topology” refers to the characterization of the physical connectivity relationships that exist among elements (e.g., devices and links) in a communication network. Discovering the physical layout and interconnections of network elements is a prerequisite to many critical network management tasks, including reactive and proactive resource management, server siting, event correlation, and root-cause analysis.
For example, consider a fault monitoring and analysis application running on a central Internet Protocol (IP) network management platform. Typically, a single fault in the network will cause a flood of alarm signals emanating from different interrelated network elements. Knowledge of network element interconnections is essential to filter out secondary alarm signals and correlate primary alarms to pinpoint the original source of failure in the network (see, Katzela, et al., “Schemes for Fault Identification in Communication Networks,” IEEE/ACM Trans. on Networking, vol. 3, no. 6, December 1995 and Yemini, et al., “High Speed & Robust Event Correlation,” IEEE Communications, 1996, incorporated herein by reference). Furthermore, a full physical map of the network enables a proactive analysis of the impact of link and device failures.
Despite the critical role of physical topology information in enhancing the manageability of modern IP networks, obtaining such information is a very difficult task. The majority of commercial network-management tools feature an IP mapping functionality for automatically discovering routers and subnets and generating a “network layer” (i.e., ISO layer-3) topology showing router-to-router interconnections and router interface-to-subnet relationships. Building a layer-3 topology is relatively easy, because routers must be explicitly aware of their neighbors to perform their basic function. Therefore, standard routing information is adequate to capture and represent layer-3 connectivity.
Unfortunately, layer-3 topology covers only a small fraction of the interrelationships in an IP network, since it fails to capture the complex interconnections of “physical layer” (i.e., ISO layer-2) network elements (switches, bridges and hubs) that comprise each Ethernet Local Area Network (LAN). Hardware providers such as Cisco and Intel have designed their own proprietary protocols for discovering physical interconnections, but these tools are of no use in a heterogeneous, multi-vendor network.
More recently, the IETF has acknowledged the importance of this problem by proposing a “physical topology” SNMP Management Information Base (MIB) (see, Bierman, et al., “Physical Topology MIB,” Internet RFC-2922, September 2000, incorporated herein by reference), but the proposal merely reserves a portion of the MIB space without defining any protocol or algorithm for obtaining the topology information. Clearly, as more switches, bridges, and hubs are deployed to provide more bandwidth through subnet microsegmentation, the portions of the network infrastructure that are “invisible” to current network-management tools will continue to grow. Under such conditions, it is obvious that the network manager's ability to troubleshoot end-to-end connectivity or assess the potential impact of link or device failures in switched networks will be severely impaired.
Developing effective algorithmic solutions for automatically discovering the up-to-date physical topology of a large, heterogeneous network poses several difficult challenges. More specifically, there are three fundamental sources of complexity for physical topology discovery.
(1) Inherent Transparency of Layer-2 Hardware. Layer-2 network elements (switches, bridges, and hubs) are completely transparent to endpoints and layer-3 hardware (routers) in the network. Switches themselves only communicate with their neighbors in the limited exchanges involved in the spanning tree protocol (see, Keshav, “An Engineering Approach to Computer Networking”, Addison-Wesley Prof. Computing Series, 1997, incorporated herein by reference), and the only state maintained is in their Address Forwarding Tables (AFTs), which are used to direct incoming packets to the appropriate output port.
Fortunately, most switches/bridges make this information available through a standard SNMP MIB (see, Case, et al., “A Simple Network Management Protocol (SNMP),” Internet RFC-1157, and, Stallings, “SNMP, SNMPv2, SNMPv3, and RMON 1 and 2”, Addison-Wesley Longman, Inc., 1999, (3rd Edition), incorporated herein by reference.)
(2) Multi-Subnet Organization. Modern switched networks usually comprise multiple subnets with elements in the same subnet communicating directly (i.e., without involving routers) whereas communication between elements in different subnets must traverse through the routers for the respective subnets. Furthermore, elements of different subnets are often directly connected to each other. This introduces serious problems for physical topology discovery, since it means that an element can be completely invisible to its direct physical neighbor(s).
(3) Transparency of “Dumb” or “Uncooperative” Elements. Besides SNMP-enabled bridges and switches that are able to provide access to their AFTs, a switched network can also deploy “dumb” elements such as hubs to interconnect switches with other switches or hosts. (Though properly designed networks would not use hubs to interconnect switches, it often occurs in practice.) Hubs do not participate in switching protocols and, thus, are essentially invisible to switches and bridges in the network. Similarly, the network may contain switches from which no address-forwarding information can be obtained either because they do not accommodate SNMP or because SNMP access to the switch is disabled. Clearly, inferring the physical interconnections of “dumb” and “uncooperative” devices based on the limited AFT information obtained from other elements poses a non-trivial algorithmic challenge.
SNMP-based algorithms for automatically discovering network layer (i.e., layer-3) topology are featured in many common network management tools, such as Hewlett Packard's OpenView and IBM's Tivoli.
Recognizing the importance of layer-2 topology, a number of vendors have recently developed proprietary tools and protocols for discovering physical network connectivity. Examples of such systems include Cisco's Discovery Protocol and Bay Networks' Optivity Enterprise. Such tools, however, require vendor-specific extensions to SNMP MIBs and are useless in a heterogeneous network comprising elements from multiple vendors in which only standard SNMP information is available.
Breitbart, et al., “Topology Discovery in Heterogeneous IP Networks,” in Proc. of IEEE INFOCOM 2000, March 2000 (incorporated herein by reference) proposed an algorithm that relies solely on standard AFT information collected in SNMP MIBs to discover the physical topology of heterogeneous networks comprising switches and bridges organized in multiple subnets. However, that algorithm assumed that AFT information is available from every node in the underlying network and thus cannot cope with hubs or uncooperative switches.
Lowekamp, et al., “Topology Discovery for Large Ethernet Networks,” in Proc. of ACM SIGCOMM, August 2001 suggested techniques for inferring network-element connectivity using incomplete AFT information and also discussed how to handle dumb/uncooperative elements. However, their algorithm is suitable only in the much simpler case of a single subnet and fails when multiple subnets are present. For instance, the Lowekamp, et al., algorithm cannot infer the topology of a network having multiple subnets, although the AFTs uniquely define the topology. Thus, the prior art contains no physical topology discovery technique that addresses all three objectives set forth above.
Accordingly, what is needed in the art is a practical, algorithmic solution for discovering the physical topology of large, heterogeneous IP networks comprising multiple subnets as well as (possibly) dumb or uncooperative elements. What is further needed in the art is a way to determine physical topology that relies substantially solely on standard information routinely collected in the SNMP MIBs of elements and that preferably requires no modifications to any operating system software running on elements or hosts.